package com.datastructures2.字符串.单词查找树;

import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;

/**
 * 基于单词查找树的符号表
 * @author MaoLin Wang
 * @date 2020/2/2611:16
 */
public class TrieST <Value>{

    /**
     * 基数
     */
    private static int R=256;
    private static Node root;

    private static class Node{
        private Object val;
        private Node[] next=new Node[R];

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", next=" + Arrays.toString(next) +
                    '}';
        }
    }

    public Value get(String key){
        Node x = get(root, key, 0);
        if (x==null){
            return null;
        }
        return (Value) x.val;
    }

    private static Node get(Node x,String key,int d){
        //返回以x作为根节点的子单词查找树中与key相关联的值
        if (x==null){
            return null;
        }
        if (d==key.length()){
            return x;
        }
        //找到第d个字符所对应的子单词查找树
        char c=key.charAt(d);
        return get(x.next[c],key,d+1);
    }

    public void  put(String key,Value val){
        root=put(root,key,val,0);
    }

    private Node put(Node x, String key, Value val, int d) {
        if (x==null){
            x=new Node();
        }
        if (d==key.length()){
            x.val=val;
            return x;
        }
        //找到第d个字符所对应的子单词查找树
        char c=key.charAt(d);
        x.next[c]=put(x.next[c],key,val,d+1);
        return x;
    }

    public static Iterable<String> keys() {
        return keysWithPrefix("");
    }

    private  static Iterable<String> keysWithPrefix(String pre) {
        Queue<String>queue=new Queue<>();
        Node x = get(root, pre, 0);
        collect(x,pre,queue);
        return queue;
    }

    private static void collect(Node x, String pre, Queue<String> queue) {
        if (x==null){
            return;
        }
        if (x.val!=null){
            queue.enqueue(pre);
        }
        for (char c = 0; c < R; c++) {
            collect(x.next[c],pre+c,queue);

        }
    }

    public Iterable<String> keysThatMatch(String pattern) {
        Queue<String> results = new Queue<String>();
        collect(root, new StringBuilder(), pattern, results);
        return results;
    }

    private void collect(Node x, StringBuilder prefix, String pattern, Queue<String> results) {
        if (x == null) return;
        int d = prefix.length();
        if (d == pattern.length() && x.val != null)
            results.enqueue(prefix.toString());
        if (d == pattern.length())
            return;
        char c = pattern.charAt(d);
        if (c == '.') {
            for (char ch = 0; ch < R; ch++) {
                prefix.append(ch);
                collect(x.next[ch], prefix, pattern, results);
                prefix.deleteCharAt(prefix.length() - 1);
            }
        }
        else {
            prefix.append(c);
            collect(x.next[c], prefix, pattern, results);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }

    public String longstPrefixOf(String s){
        int length=search(root,s,0,0);
        return s.substring(0,length);
    }

    private int search(Node root, String s, int d, int length) {
        if (root==null){
            return length;
        }
        if (root.val!=null){
            length=d;
        }
        if (d==s.length()){
            return length;
        }
        char c=s.charAt(d);
        return search(root.next[c],s,d+1,length);
    }
    public static void  delete(String key){
        root=delete(root,key,0);
    }

    private static Node delete(Node root, String key, int d) {
        if (root==null){
            return null;
        }
        if (d==key.length()){
            root.val=null;
        }else {
            char c=key.charAt(d);
            delete(root.next[c],key,d+1);
        }
        if (root.val!=null)
            return root;
        for (char c = 0; c < R; c++) {
            if (root.next[c]!=null)
            {
                return root;
            }
        }

        return null;
    }


    public static void main(String[] args) {
        TrieST<Integer> trieST=new TrieST<>();
        trieST.put("shells",3);
        trieST.put("she",0);
        trieST.put("sea",2);
        trieST.put("sells",1);
        //String shella = trieST.longstPrefixOf("shella");
       // System.out.println(shella);

        Integer shells = trieST.get("shells");
        System.out.println(shells);
        delete("shells");
        shells = trieST.get("shells");
        System.out.println(shells);


    }
}
